2016-12-13

Замена Heap на преалоцированный Vec + Lifetime переменные

TL;DR: Такой рефакторинг привел всех в состояние Х. С 7мкс до 200нс (буст в 35 раз). В вопросе скорости создания контекстов мы выебали Kx Systems, Erlang и Python. На этом можно поставить пока точку.


Lang    avg ns of 1M calls
------- ------------------
Rust    0
Java    3
O-CPS   217
Erlang  10699/1806/436/9
Python  537
K       899
LuaJIT  33856

Мы поменяли в нашем интерпретаторе все Box Heap аллокации на преалоцированный ручной хип с вектором указателей + лайфтайм по всему коду. Т.е. даже Box остались исключительно как бинды. Получился Zero-Copy Interpreter работающий исключительно с указателями на ячейки байт-кода виртуальной машины, которые в сущности сериализированные элементы AST дерева. Опуская детали реализации приведу только типы деревьев:

Старое дерево с Heap указателями


pub enum Cont {
    Expressions(AST, Tape),
    Lambda(Code, AST, AST, Tape),
    Assign(AST, Tape),
    Cond(AST, AST, Tape),
    Func(AST, AST, Tape),
    Call(AST, Tape),
    Verb(Verb, AST, u8, Tape),
    Adverb(Adverb, AST, Tape),
    Return,
}

pub struct Tape {
    env: Rc>,
    cont: Box,
}

Новое дерево только с абстрактными ссылками и переменными времени жизни


pub enum Cont<'a> {
    Expressions(&'a AST<'ast>, &'a Cont<'a>),
    Lambda(Code, &'a AST<'a>, &'a AST<'a>, &'a Cont<'a>),
    Assign(&'a AST<'ast>, &'ast Cont<'ast>),
    Cond(&'a AST<'a>, &'a AST<'a>, &'a Cont<'a>),
    Func(&'a AST<'a>, &'a AST<'a>, &'a Cont<'a>),
    Call(&'a AST<'a>, &'a Cont<'a>),
    Verb(Verb, &'a AST<'a>, u8, &'a Cont<'a>),
    Adverb(Adverb, &'a AST<'a>, &'a Cont<'a>),
    Return,
}

pub struct Interpreter<'a> {
    arena: Arena<'a>,
    env: Environment<'a>,
}

Environment в наивном прототипе представлен в виде HashMap, который как известно неподходит там где нужна скорость, зато понятно — у каждой кложи своя хеш-таблица контекст. Другое дело что для этого всего хватит и стека фреймов. Вообще говоря контексты функций — это и есть стек, а перенесен он в Heap для того, чтобы можно было писать не валящиеся бесконечные циклы, что называется tailcall или CPS интерпретаторами.

Написать прототип на расте оказалось очень просто. Бездумный ленивый CPS интерпретатор, который в хипе держит свой стек в виде HashMap изначально является не хуже чем LuaJIT в вопросе создания контекстов, а переписанный нормально в zero-copy версию с лайфтаймами с стек-фреймами в преалоцированном векторе обгоняет даже лидеров индустрии.

В рабочем режиме расставить амперсанты по коду заняло приблизительно 3 дня (чтобы получить 200нс версию), столько же времени ушло на создание изначального 7мкс прототипа. За скобками осталось влияние замены хештаблиц в качестве носителей контекстов на стековые фреймы в носителе-векторе, думаю заслуга этой части тоже немалая.

Это не первый интерпретатор с монотонно-растущими адресами, а значит существует функция ограничивающая расстояние до самого древнего индекса в ленте интерпретатора, на который хоть кто-то ссылается. Хочется сделать так чтобы расстояние до этого самого древнего индекса всегда было меньше N, чтобы закольцевать и замуровать его в ограниченном буфере-очереди-стриме. Сам интерпретатор является продюсером и консамером четырех стримов, т.е. его устройство полностью линеаризировано.